package binarytree

// 思路
// 自底向上依赖子树反馈的包含的目标节点来判断
// 如果两棵子树都告知了有目标节点，那当前节点就是真正的终极目标；
// 如果其中一颗告知了，看看当前节点是不是目标节点，如果不是原样返回子树节点(未必是终极节点），如果是的话，修正为当前节点(终极节点)。
// 反正pq肯定在树中，说明一定能找到，就这么返回就行，最终返回的肯定就是了，不管是不是确定的终极节点。
func lowestCommonAncestorSelf(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	if root == p || root == q {
		return root
	}

	left := lowestCommonAncestorSelf(root.Left, p, q)
	right := lowestCommonAncestorSelf(root.Right, p, q)

	if left != nil && right != nil {
		return root
	} else if left != nil {
		return left
	} else if right != nil {
		return right
	}

	return nil
}
